package cn.kent.simple;

import java.util.HashSet;

/**
 * 160. 相交链表
 * @author kent
 */
public class GetIntersectionNode {
    /**
     * 0ms
     * 分情况讨论, 双指针方法其实也是这样分析的过程, 分两大类情况:
     * 1. 长度一致
     *      相交  |  不相交
     * 2. 长度不一致
     *      算长度差值, 按照长度一致进行计算
     */
    public static ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int la = 0, lb = 0;
        int dis = 0;
        ListNode ha = headA, hb = headB;
        while (ha != null) {
            la++;
            ha = ha.next;
        }
        while (hb != null) {
            lb++;
            hb = hb.next;
        }
        if (la > lb) {
            ha = headA;
            hb = headB;
            dis = la - lb;
        } else {
            ha = headB;
            hb = headA;
            dis = lb - la;
        }
        for (int i = 0; i < dis; i++)
            ha = ha.next;
        while (ha != hb) {
            ha = ha.next;
            hb = hb.next;
        }
        return ha;
    }

    /**
     * 双指针
     * 分析流程: 分析步骤同第三个方法, 长度不一致时, 一直追, 追a+b+c (说明:a+c=m, b+c=n)次到相交点相等->返回
     * 时间复杂度: O(m+n)  m,n分别是AB链表的长度, 两个指针分别遍历两个链表, 每个指针遍历两个链表一次
     * 空间复杂度: O(1)
     */
    public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    /**
     * 哈希表
     * 时间复杂度: O(m+n)
     * 空间复杂度: O(m) m 代表链表A的长度, 因为将链表A存入了哈希表
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode tmp = headA;
        while (tmp != null) {
            set.add(tmp);
            tmp = tmp.next;
        }
        tmp = headB;
        while (tmp != null) {
            if (set.contains(tmp))
                return tmp;
            tmp = tmp.next;
        }
        return null;
    }


    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
